package com.zhupf.binaryTree;


import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhupf
 * @date 2023年11月28日 10:09
 * @Description.
 *  98、验证搜索二叉树
 */
public class IsValidBST {

    public static void main(String[] args) {
        TreeNode root =  new TreeNode(5,new TreeNode(1),new TreeNode(4,new TreeNode(3),new TreeNode(6)));
        isValidBST2(root);
    }

    public static boolean isValidBST(TreeNode root) {

        return process(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    public static boolean process(TreeNode root ,long min, long max){
        if(root == null){
            return true;
        }
        if(root.val <= min || root.val >= max){
            return false;
        }
        return process(root.left,min,root.val) && process(root.right,root.val,max);
    }

    public static boolean isValidBST2(TreeNode root) {
        Deque<TreeNode> stk = new LinkedList<>();
        Long pre = Long.MIN_VALUE;
        while (!stk.isEmpty() || root != null){
            while (root != null){
                stk.push(root);
                root = root.left;
            }
            root = stk.poll();
            if(root.val <= pre){
                return false;
            }
            pre = root.val+0L;
            root = root.right;
        }
        return true;
    }
}
